class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        // 状态表示 - 以 i 位置为结尾的摆动序列的最大长度
        int[] f = new int[n];
        int[] g = new int[n];
        // 初始化
        for(int i = 0; i < n; i++){
            f[i] = 1;
            g[i] = 1;
        }
        // 状态转移方程
        int ret = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] < nums[j]){
                    g[i] = Math.max(g[i], f[j] + 1);
                }
                if(nums[i] > nums[j]){
                    f[i] = Math.max(f[i], g[j] + 1);
                }
            }
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }
}